package com.github.sort;

public class HeapSort {
    public static void heapSort(Comparable[] R){
        int i,n=R.length-1;
        for (i = n/2; i >=1 ; i--) {
            sift(R,i,n);
        }
        for (i = n; i >=2 ; i--) {
            exch(R,i);
            sift(R,1,i-1);
        }
    }
    private static void sift(Comparable[] R, int low,int high){
        int i=low,j=2*i;
        Comparable temp=R[i];
        while (j<=high){
            if (j<high&&less(R[j],R[j+1]))j++;
            if (less(temp,R[j])){
                R[i]=R[j];
                i=j;
                j=2*i;
            }else
                break;
        }
        R[i]=temp;
    }
   private static void exch(Comparable[]R,int i){
        Comparable tmp=R[1];
        R[1]=R[i];
        R[i]=tmp;
   }
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
}
